package com.sheng.leetcode.year2023.month03.day28;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/28
 * <p>
 * 1092. 最短公共超序列<p>
 * <p>
 * 给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。<p>
 * （如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）<p>
 * <p>
 * 示例：<p>
 * 输入：str1 = "abac", str2 = "cab"<p>
 * 输出："cabac"<p>
 * 解释：<p>
 * str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。<p>
 * str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。<p>
 * 最终我们给出的答案是满足上述属性的最短字符串。<p>
 * <p>
 * 提示：<p>
 * 1 <= str1.length, str2.length <= 1000<p>
 * str1 和 str2 都由小写英文字母组成。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shortest-common-supersequence">1092. 最短公共超序列</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1092 {

    @Test
    public void test01() {
        String str1 = "abac", str2 = "cab";
        System.out.println(new Solution().shortestCommonSupersequence(str1, str2));
    }
}

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        // f[i][j] 表示字符串 str1 的前 i 个字符和字符串 str2 的前 j 个字符的最长公共子序列的长度
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        // 双指针 i， j 指向 str1 和 str2 的末尾，从后往前遍历，比较 str1[i] 和 str2[j] 的值
        int i = m, j = n;
        StringBuilder ans = new StringBuilder();
        while (i > 0 || j > 0) {
            // 如果 str1[i] = str2[j]，则将 str1[i] 或 str2[j] 中的任意一个字符加入到答案序列，然后 i 和 j 同时减 1；
            // 如果 str1[i] != str2[j]，则将 f[i][j] 与 f[i−1][j] 和 f[i][j−1] 中的最大值进行比较：
            // 如果 f[i][j] = f[i−1][j]，则将 str1[i] 加入到答案序列，然后 i 减1；
            // 如果 f[i][j] = f[i][j−1]，则将 str2[j] 加入到答案序列，然后 j 减1。
            // 重复上述操作，直到 i = 0 或 j = 0 ，然后将剩余的字符串加入到答案序列即可。
            // 最后我们将答案序列反转，即可得到最终的答案。
            if (i == 0) {
                ans.append(str2.charAt(--j));
            } else if (j == 0) {
                ans.append(str1.charAt(--i));
            } else {
                if (f[i][j] == f[i - 1][j]) {
                    ans.append(str1.charAt(--i));
                } else if (f[i][j] == f[i][j - 1]) {
                    ans.append(str2.charAt(--j));
                } else {
                    ans.append(str1.charAt(--i));
                    --j;
                }
            }
        }
        return ans.reverse().toString();
    }
}
